package uba.algo3.tp3.tsp;

import java.util.ArrayList;

public class Constructiva
{
	private Grafo g;
	int costoMin = Integer.MAX_VALUE;

	public Grafo getG()
	{
		return g;
	}

	public void setG(Grafo g)
	{
		this.g = g;
	}
	
	public Constructiva(Grafo g)
	{
        this.g = g;
	}
	
	public Solucion get2TSP()
	{
		int n = g.getN();
		int i = 3;
		int tam_part1 = n + 1 - i, tam_part2 = 3;
		int costoMinTotal = Integer.MAX_VALUE;
		Solucion solFinal = null;
		
		while(tam_part1 >= tam_part2)
		{
			
			Solucion s_part = solucion_golosa(tam_part1, tam_part2);//O(n^2)
			int costoTotal = s_part.getCosto(); 
			
			if(costoTotal < costoMinTotal){
			
				solFinal = s_part;
				costoMinTotal = costoTotal;
				costoMin = costoTotal;
			}
			
			i++;
			
			tam_part1 = n + 1 - i;
			tam_part2 = i;
		}
		
		return solFinal;
	}

	private Solucion solucion_golosa(int tam_part1, int tam_part2)
	{
		int nodo_orig = g.getOrig();

		ArrayList<Integer> solucion_parcial = new ArrayList<Integer>();
		
		solucion_parcial.add(nodo_orig);
		
		int anterior = nodo_orig;
		int actual;
		
		while(solucion_parcial.size() != tam_part1)//O(n)
		{
			actual = menorPeso(anterior,solucion_parcial);//O(n)
			if(actual == 0)
			{
				System.out.println("Error");
			}
			else
			{
				solucion_parcial.add(actual);	
			}
			anterior = actual;
		}//O(n^2)
		
		ArrayList<Integer> solucion_parcial2 = new ArrayList<Integer>();
		anterior = nodo_orig;
		ArrayList<Integer> nodos_visitados = (ArrayList<Integer>) solucion_parcial.clone();//O(n)
		solucion_parcial2.add(nodo_orig);
		
		while(solucion_parcial2.size() != tam_part2)//O(n)
		{
			actual = menorPeso(anterior,nodos_visitados);//O(n)
			if(actual == 0)
			{
				System.out.println("Error");
			}
			else
			{
				solucion_parcial2.add(actual);
				nodos_visitados.add(actual);
			}
			anterior = actual;
		}
		int costo = g.calcular_costo(solucion_parcial) + g.calcular_costo(solucion_parcial2);//O(n)
		Solucion sol = new Solucion(solucion_parcial,solucion_parcial2,costo);
		
		return sol;
	}

	private int menorPeso(int anterior, ArrayList<Integer> solucion_p)
	{
		int min = Integer.MAX_VALUE;
		int temp;
		int res = -1;
		int n = g.getN();
		
		for(int j = 0; j<n;j++)//O(n)
		{
			if(!solucion_p.contains(j+1))//O(n)..se podria implementar facilmente en O(1) con un arreglo de bools..TODO
			{
				temp = g.matriz[anterior-1][j];
				if(temp < min)
				{
					min = temp;
					res = j+1;
				}
			}
		}
		return res;
	}
	
}
